package j2025.j03;

import java.nio.channels.NonReadableChannelException;
import java.util.ArrayList;
import java.util.List;

/**
 * @Author 猫大仙
 * 
 */
 public class j0305 {
 public String gcdOfStrings(String str1, String str2) {
  int l1 = str1.length(),l2 = str2.length();
  for (int i = Math.min(l1,l2); i >= 0; i--) {
   if(l1%i == 0 && l2%i == 0){
    String s = str1.substring(0,i);
    if(check(s,str1) && check(s,str2)){
     return s;
    }
   }
  }
  return "";
 }
 public boolean check(String t, String s) {
  int lenx = s.length() / t.length();
  StringBuffer ans = new StringBuffer();
  for (int i = 1; i <= lenx; ++i) {
   ans.append(t);
  }
  return ans.toString().equals(s);
 }

 public String minWindow(String s, String t) {
  int lens = s.length();
  int lent = t.length();
  int[] hash1 = new int[128];
  int[] hash2 = new int[128];
  char[] ss = s.toCharArray();
  char[] tt = t.toCharArray();
  int kind = 0,begin = -1,minlen = Integer.MAX_VALUE;
  for (int i = 0; i < lent; i++) {
   if(hash2[tt[i]]==0){
    kind++;
   }
   hash2[tt[i]]++;
  }
  for (int left = 0,right = 0,count = 0; right<lens ; right++) {
   char in = ss[right];
   hash1[in]++;
   if(hash1[in]==hash2[in]){
    count++;
   }
   while(count==kind){
    //更新数据
    int len = right-left+1;
    if(len<minlen){
     minlen = len;
     begin = left;
    }
    char out = ss[left++];
    if(hash2[out]==hash1[out]){
     count--;
    }
    hash1[out]--;
   }
  }
  if(begin == -1){
   return "";
  }else {
   return s.substring(begin,begin+minlen);
  }

 }


    public List<Integer> spiralOrder(int[][] matrix) {
        int m = matrix.length,n = matrix[0].length;
        int left = 0,right = n-1,top = 0,bottom = m-1;
        List<Integer> ret = new ArrayList<>();
        while(true){
         for (int i = left; i <= right; i++) {
          ret.add(matrix[top][i]);
         }
         if(++top>bottom)  break;
         for (int i = top; i <= bottom; i++) {
          ret.add(matrix[i][right]);
         }
         if(--right<left) break;
         for (int i = right; i >= left; i--) {
          ret.add(matrix[bottom][i]);
         }
         if(--bottom<top) break;
         for (int i = bottom; i >= top; i--) {
          ret.add(matrix[i][left]);
         }
         if(++left>right) break;
        }
        return ret;
    }
}
